SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Random sample consensus</title>

</head>

Random sample consensus

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1246091330">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r886047488">

/* start https://en.wikipedia.org/ */

.mw-parser-output .nobold{font-weight:normal}

/* end https://en.wikipedia.org/ */

</style><table class="sidebar sidebar-collapse nomobile nowraplinks"><tbody><tr><td class="sidebar-pretitle">Part of a series on</td></tr><tr><th class="sidebar-title-with-pretitle"><a href="Machine_learning" title="Machine learning">Machine learning</a> and <a href="Data_mining" title="Data mining">data mining</a></th></tr><tr><td class="sidebar-content">

<ul><li><a href="Supervised_learning" title="Supervised learning">Supervised learning</a></li>

<li><a href="Unsupervised_learning" title="Unsupervised learning">Unsupervised learning</a></li>

<li><a href="Semi-supervised_learning" class="mw-redirect" title="Semi-supervised learning">Semi-supervised learning</a></li>

<li><a href="Self-supervised_learning" title="Self-supervised learning">Self-supervised learning</a></li>

<li><a href="Reinforcement_learning" title="Reinforcement learning">Reinforcement learning</a></li>

<li><a href="Meta-learning_(computer_science)" title="Meta-learning (computer science)">Meta-learning</a></li>

<li><a href="Online_machine_learning" title="Online machine learning">Online learning</a></li>

<li><a href="Batch_learning" class="mw-redirect" title="Batch learning">Batch learning</a></li>

<li><a href="Curriculum_learning" title="Curriculum learning">Curriculum learning</a></li>

<li><a href="Rule-based_machine_learning" title="Rule-based machine learning">Rule-based learning</a></li>

<li><a href="Neuro-symbolic_AI" title="Neuro-symbolic AI">Neuro-symbolic AI</a></li>

<li><a href="Neuromorphic_engineering" class="mw-redirect" title="Neuromorphic engineering">Neuromorphic engineering</a></li>

<li><a href="Quantum_machine_learning" title="Quantum machine learning">Quantum machine learning</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<ul><li><a href="Statistical_classification" title="Statistical classification">Classification</a></li>

<li><a href="Generative_model" title="Generative model">Generative modeling</a></li>

<li><a href="Regression_analysis" title="Regression analysis">Regression</a></li>

<li><a href="Cluster_analysis" title="Cluster analysis">Clustering</a></li>

<li><a href="Dimensionality_reduction" title="Dimensionality reduction">Dimensionality reduction</a></li>

<li><a href="Density_estimation" title="Density estimation">Density estimation</a></li>

<li><a href="Anomaly_detection" title="Anomaly detection">Anomaly detection</a></li>

<li><a href="Data_cleaning" class="mw-redirect" title="Data cleaning">Data cleaning</a></li>

<li><a href="Automated_machine_learning" title="Automated machine learning">AutoML</a></li>

<li><a href="Association_rule_learning" title="Association rule learning">Association rules</a></li>

<li><a href="Semantic_analysis_(machine_learning)" title="Semantic analysis (machine learning)">Semantic analysis</a></li>

<li><a href="Structured_prediction" title="Structured prediction">Structured prediction</a></li>

<li><a href="Feature_engineering" title="Feature engineering">Feature engineering</a></li>

<li><a href="Feature_learning" title="Feature learning">Feature learning</a></li>

<li><a href="Learning_to_rank" title="Learning to rank">Learning to rank</a></li>

<li><a href="Grammar_induction" title="Grammar induction">Grammar induction</a></li>

<li><a href="Ontology_learning" title="Ontology learning">Ontology learning</a></li>

<li><a href="Multimodal_learning" title="Multimodal learning">Multimodal learning</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><div style="display: inline-block; line-height: 1.2em; padding: .1em 0;"><a href="Supervised_learning" title="Supervised learning">Supervised learning</a> (<a href="Statistical_classification" title="Statistical classification">classification</a> • <a href="Regression_analysis" title="Regression analysis">regression</a>) </div></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Apprenticeship_learning" title="Apprenticeship learning">Apprenticeship learning</a></li>

<li><a href="Decision_tree_learning" title="Decision tree learning">Decision trees</a></li>

<li><a href="Ensemble_learning" title="Ensemble learning">Ensembles</a>

<ul><li><a href="Bootstrap_aggregating" title="Bootstrap aggregating">Bagging</a></li>

<li><a href="Boosting_(machine_learning)" title="Boosting (machine learning)">Boosting</a></li>

<li><a href="Random_forest" title="Random forest">Random forest</a></li></ul></li>

<li><a href="Linear_regression" title="Linear regression">Linear regression</a></li>

<li><a href="Naive_Bayes_classifier" title="Naive Bayes classifier">Naive Bayes</a></li>

<li><a href="Artificial_neural_network" class="mw-redirect" title="Artificial neural network">Artificial neural networks</a></li>

<li><a href="Logistic_regression" title="Logistic regression">Logistic regression</a></li>

<li><a href="Perceptron" title="Perceptron">Perceptron</a></li>

<li><a href="Relevance_vector_machine" title="Relevance vector machine">Relevance vector machine (RVM)</a></li>

<li><a href="Support_vector_machine" title="Support vector machine">Support vector machine (SVM)</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Cluster_analysis" title="Cluster analysis">Clustering</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="BIRCH" title="BIRCH">BIRCH</a></li>

<li><a href="Hierarchical_clustering" title="Hierarchical clustering">Hierarchical</a></li>

<li><a href="K-means_clustering" title="K-means clustering">k-means</a></li>

<li><a href="Fuzzy_clustering" title="Fuzzy clustering">Fuzzy</a></li>

<li><a href="Expectation%E2%80%93maximization_algorithm" title="Expectation–maximization algorithm">Expectation–maximization (EM)</a></li>

<li> <a href="DBSCAN" title="DBSCAN">DBSCAN</a></li>

<li><a href="OPTICS_algorithm" title="OPTICS algorithm">OPTICS</a></li>

<li><a href="Mean_shift" title="Mean shift">Mean shift</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Dimensionality_reduction" title="Dimensionality reduction">Dimensionality reduction</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Factor_analysis" title="Factor analysis">Factor analysis</a></li>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Structured_prediction" title="Structured prediction">Structured prediction</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Graphical_model" title="Graphical model">Graphical models</a>

<ul><li><a href="Bayesian_network" title="Bayesian network">Bayes net</a></li>

<li><a href="Conditional_random_field" title="Conditional random field">Conditional random field</a></li>

<li><a href="Hidden_Markov_model" title="Hidden Markov model">Hidden Markov</a></li></ul></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Anomaly_detection" title="Anomaly detection">Anomaly detection</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul>

<li><a href="Local_outlier_factor" title="Local outlier factor">Local outlier factor</a></li>

<li><a href="Isolation_forest" title="Isolation forest">Isolation forest</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Neural_network_(machine_learning)" title="Neural network (machine learning)">Neural networks</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Autoencoder" title="Autoencoder">Autoencoder</a></li>

<li><a href="Deep_learning" title="Deep learning">Deep learning</a></li>

<li><a href="Feedforward_neural_network" title="Feedforward neural network">Feedforward neural network</a></li>

<li><a href="Recurrent_neural_network" title="Recurrent neural network">Recurrent neural network</a>

<li><a href="Reservoir_computing" title="Reservoir computing">reservoir computing</a></li></ul></li>

<li><a href="Boltzmann_machine" title="Boltzmann machine">Boltzmann machine</a>

<ul><li><a href="Restricted_Boltzmann_machine" title="Restricted Boltzmann machine">Restricted</a></li></ul></li>

<li><a href="Diffusion_model" title="Diffusion model">Diffusion model</a></li>

<li><a href="Convolutional_neural_network" title="Convolutional neural network">Convolutional neural network</a>

<li><a href="LeNet" title="LeNet">LeNet</a></li>

<li><a href="AlexNet" title="AlexNet">AlexNet</a></li>

<li><a href="DeepDream" title="DeepDream">DeepDream</a></li></ul></li>

<li><a href="Neural_field" title="Neural field">Neural field</a>

<ul><li><a href="Neural_radiance_field" title="Neural radiance field">Neural radiance field</a></li>

<li><a href="Physics-informed_neural_networks" title="Physics-informed neural networks">Physics-informed neural networks</a></li></ul></li>

<li><a href="Transformer_(deep_learning_architecture)" title="Transformer (deep learning architecture)">Transformer</a>

<ul><li><a href="Vision_transformer" title="Vision transformer">Vision</a></li></ul></li>

<li><a href="Mamba_(deep_learning_architecture)" title="Mamba (deep learning architecture)">Mamba</a></li>

<li><a href="Spiking_neural_network" title="Spiking neural network">Spiking neural network</a></li>

<li><a href="Memtransistor" title="Memtransistor">Memtransistor</a></li>

<li><a href="Electrochemical_RAM" title="Electrochemical RAM">Electrochemical RAM</a> (ECRAM)</li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Reinforcement_learning" title="Reinforcement learning">Reinforcement learning</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Q-learning" title="Q-learning">Q-learning</a></li>

<li><a href="Policy_gradient_method" title="Policy gradient method">Policy gradient</a></li>

<li><a href="State%E2%80%93action%E2%80%93reward%E2%80%93state%E2%80%93action" title="State–action–reward–state–action">SARSA</a></li>

<li><a href="Temporal_difference_learning" title="Temporal difference learning">Temporal difference (TD)</a></li>

<li><a href="Multi-agent_reinforcement_learning" title="Multi-agent reinforcement learning">Multi-agent</a>

</tr><tr><td class="sidebar-content">

<ul><li><a href="Active_learning_(machine_learning)" title="Active learning (machine learning)">Active learning</a></li>

<li><a href="Crowdsourcing" title="Crowdsourcing">Crowdsourcing</a></li>

<li><a href="Human-in-the-loop" title="Human-in-the-loop">Human-in-the-loop</a></li>

<li><a href="Mechanistic_interpretability" title="Mechanistic interpretability">Mechanistic interpretability</a></li>

</tr><tr><td class="sidebar-content">

<ul><li><a href="Coefficient_of_determination" title="Coefficient of determination">Coefficient of determination</a></li>

<li><a href="Confusion_matrix" title="Confusion matrix">Confusion matrix</a></li>

<li><a href="Learning_curve_(machine_learning)" title="Learning curve (machine learning)">Learning curve</a></li>

<li><a href="Receiver_operating_characteristic" title="Receiver operating characteristic">ROC curve</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Mathematical foundations</div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Kernel_machines" class="mw-redirect" title="Kernel machines">Kernel machines</a></li>

<li><a href="Bias%E2%80%93variance_tradeoff" title="Bias–variance tradeoff">Bias–variance tradeoff</a></li>

<li><a href="Computational_learning_theory" title="Computational learning theory">Computational learning theory</a></li>

<li><a href="Empirical_risk_minimization" title="Empirical risk minimization">Empirical risk minimization</a></li>

<li><a href="Occam_learning" title="Occam learning">Occam learning</a></li>

<li><a href="Probably_approximately_correct_learning" title="Probably approximately correct learning">PAC learning</a></li>

<li><a href="Statistical_learning_theory" title="Statistical learning theory">Statistical learning</a></li>

<li><a href="Vapnik%E2%80%93Chervonenkis_theory" title="Vapnik–Chervonenkis theory">VC theory</a></li>

<li><a href="Topological_deep_learning" title="Topological deep learning">Topological deep learning</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Journals and conferences</div><div class="sidebar-list-content mw-collapsible-content hlist">

<li><a href="Conference_on_Neural_Information_Processing_Systems" title="Conference on Neural Information Processing Systems">NeurIPS</a></li>

<li><a href="International_Joint_Conference_on_Artificial_Intelligence" title="International Joint Conference on Artificial Intelligence">IJCAI</a></li>

</tr><tr><td class="sidebar-content">

<ul><li><a href="Glossary_of_artificial_intelligence" title="Glossary of artificial intelligence">Glossary of artificial intelligence</a></li>

<li><a href="List_of_datasets_for_machine-learning_research" title="List of datasets for machine-learning research">List of datasets for machine-learning research</a>

<ul><li><a href="List_of_datasets_in_computer_vision_and_image_processing" title="List of datasets in computer vision and image processing">List of datasets in computer vision and image processing</a></li></ul></li>

<li><a href="Outline_of_machine_learning" title="Outline of machine learning">Outline of machine learning</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-navbar"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></td></tr></tbody></table>

Random sample consensus (RANSAC) is an <a href="Iterative_method" title="Iterative method">iterative method</a> to estimate parameters of a mathematical model from a set of observed data that contains <a href="Outliers" class="mw-redirect" title="Outliers">outliers</a>, when outliers are to be accorded no influence on the values of the estimates. Therefore, it also can be interpreted as an outlier detection method.<a href="#cite_note-1">[1]</a> It is a non-deterministic algorithm in the sense that it produces a reasonable result only with a certain probability, with this probability increasing as more iterations are allowed. The algorithm was first published by Fischler and Bolles at <a href="SRI_International" title="SRI International">SRI International</a> in 1981. They used RANSAC to solve the location determination problem (LDP), where the goal is to determine the points in the space that project onto an image into a set of landmarks with known locations.

RANSAC uses <a href="Cross-validation_(statistics)#Repeated_random_sub-sampling_validation" title="Cross-validation (statistics)">repeated random sub-sampling</a>.<a href="#cite_note-2">[2]</a> A basic assumption is that the data consists of "inliers", i.e., data whose distribution can be explained by some set of model parameters, though may be subject to noise, and "outliers", which are data that do not fit the model. The outliers can come, for example, from extreme values of the noise or from erroneous measurements or incorrect hypotheses about the interpretation of data. RANSAC also assumes that, given a (usually small) set of inliers, there exists a procedure that can estimate the parameters of a model optimally explaining or fitting this data.

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

A simple example is <a href="Regression_analysis" title="Regression analysis">fitting a line</a> in two dimensions to a set of observations. Assuming that this set contains both inliers, i.e., points which approximately can be fitted to a line, and outliers, points which cannot be fitted to this line, a <a href="Ordinary_least_squares" title="Ordinary least squares">simple least squares method</a> for line fitting will generally produce a line with a bad fit to the data including inliers and outliers. The reason is that it is optimally fitted to all points, including the outliers. RANSAC, on the other hand, attempts to exclude the outliers and find a linear model that only uses the inliers in its calculation. This is done by fitting linear models to several random samplings of the data and returning the model that has the best fit to a subset of the data. Since the inliers tend to be more linearly related than a random mixture of inliers and outliers, a random subset that consists entirely of inliers will have the best model fit. In practice, there is no guarantee that a subset of inliers will be randomly sampled, and the probability of the algorithm succeeding depends on the proportion of inliers in the data as well as the choice of several algorithm parameters.

<div class="gallerytext">A data set with many outliers for which a line has to be fitted.</div>

</li>

<div class="gallerytext">Fitted line with RANSAC; outliers have no influence on the result.</div>

</li>

</ul>

<div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2></div>

The RANSAC algorithm is a learning technique to estimate parameters of a model by random sampling of observed data. Given a dataset whose data elements contain both inliers and outliers, RANSAC uses the voting scheme to find the optimal fitting result. Data elements in the dataset are used to vote for one or multiple models. The implementation of this voting scheme is based on two assumptions: that the noisy features will not vote consistently for any single model (few outliers) and there are enough features to agree on a good model (few missing data). The RANSAC algorithm is essentially composed of two steps that are iteratively repeated:

<ol><li>A sample subset containing minimal number of data items is randomly selected from the input dataset. A fitting model with model parameters is computed using only the elements of this sample subset. The cardinality of the sample subset (e.g., the amount of data in this subset) is sufficient to determine the model parameters.</li>

<li>The algorithm checks which elements of the entire dataset are consistent with the model instantiated by the estimated model parameters obtained from the first step. A data element will be considered as an outlier if it does not fit the model within some error threshold defining the maximum data deviation of inliers (data elements beyond this deviation are outliers).</li></ol>

The set of inliers obtained for the fitting model is called the consensus set. The RANSAC algorithm will iteratively repeat the above two steps until the obtained consensus set in certain iteration has enough inliers.

The input to the RANSAC algorithm is a set of observed data values, a model to fit to the observations, and some <a href="Confidence_interval" title="Confidence interval">confidence</a> parameters defining outliers. In more details than the aforementioned RANSAC algorithm overview, RANSAC achieves its goal by repeating the following steps:

<ol><li>Select a random subset of the original data. Call this subset the hypothetical inliers.</li>

<li>A model is fitted to the set of hypothetical inliers.</li>

<li>All data are then tested against the fitted model. All the data points (of the original data) that fit the estimated model well, according to some model-specific <a href="Loss_function" title="Loss function">loss function</a>, are called the consensus set (i.e., the set of inliers for the model).</li>

<li>The estimated model is reasonably good if sufficiently many data points have been classified as a part of the consensus set.</li>

<li>The model may be improved by re-estimating it by using all the members of the consensus set. The fitting quality as a measure of how well the model fits to the consensus set will be used to sharpen the model fitting as iterations goes on (e.g., by setting this measure as the fitting quality criteria at the next iteration).</li></ol>

To converge to a sufficiently good model parameter set, this procedure is repeated a fixed number of times, each time producing either the rejection of a model because too few points are a part of the consensus set, or a refined model with a consensus set size larger than the previous consensus set.

<div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2></div>

The generic RANSAC algorithm works as the following <a href="Pseudocode" title="Pseudocode">pseudocode</a>:

<pre>Given:

data – A set of observations.

model – A model to explain the observed data points.

n – The minimum number of data points required to estimate the model parameters.

k – The maximum number of iterations allowed in the algorithm.

t – A threshold value to determine data points that are fit well by the model (inlier).

d – The number of close data points (inliers) required to assert that the model fits well to the data.

Return:

bestFit – The model parameters which may best fit the data (or null if no good model is found).

iterations = 0

bestFit = null

bestErr = something really large // This parameter is used to sharpen the model parameters to the best data fitting as iterations go on.

while iterations < k do

maybeInliers := n randomly selected values from data

maybeModel := model parameters fitted to maybeInliers

confirmedInliers := empty set

for every point in data do

if point fits maybeModel with an error smaller than t then

add point to confirmedInliers

end if

end for

if the number of elements in confirmedInliers is > d then

// This implies that we may have found a good model.

// Now test how good it is.

betterModel := model parameters fitted to all the points in confirmedInliers

thisErr := a measure of how well betterModel fits these points

if thisErr < bestErr then

bestFit := betterModel

bestErr := thisErr

end if

increment iterations

end while

return bestFit

</pre>

<div class="mw-heading mw-heading2"><h2 id="Example_code">Example code</h2></div>

A Python implementation mirroring the pseudocode. This also defines a <code>LinearRegressor</code> based on least squares, applies <code>RANSAC</code> to a 2D regression problem, and visualizes the outcome:

<div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre>from copy import copy

import numpy as np

from numpy.random import default_rng

rng = default_rng()

class RANSAC:

def __init__(self, n=10, k=100, t=0.05, d=10, model=None, loss=None, metric=None):

self.n = n # `n`: Minimum number of data points to estimate parameters

self.k = k # `k`: Maximum iterations allowed

self.t = t # `t`: Threshold value to determine if points are fit well

self.d = d # `d`: Number of close data points required to assert model fits well

self.model = model # `model`: class implementing `fit` and `predict`

self.loss = loss # `loss`: function of `y_true` and `y_pred` that returns a vector

self.metric = metric # `metric`: function of `y_true` and `y_pred` and returns a float

self.best_fit = None

self.best_error = np.inf

for _ in range(self.k):

ids = rng.permutation(X.shape[0])

maybe_inliers = ids[: self.n]

maybe_model = copy(self.model).fit(X[maybe_inliers], y[maybe_inliers])

thresholded = (

self.loss(y[ids][self.n :], maybe_model.predict(X[ids][self.n :]))

< self.t

)

inlier_ids = ids[self.n :][np.flatnonzero(thresholded).flatten()]

if inlier_ids.size > self.d:

inlier_points = np.hstack([maybe_inliers, inlier_ids])

better_model = copy(self.model).fit(X[inlier_points], y[inlier_points])

this_error = self.metric(

y[inlier_points], better_model.predict(X[inlier_points])

)

if this_error < self.best_error:

self.best_error = this_error

self.best_fit = better_model

return self

return self.best_fit.predict(X)

def square_error_loss(y_true, y_pred):

return (y_true - y_pred) ** 2

def mean_square_error(y_true, y_pred):

return np.sum(square_error_loss(y_true, y_pred)) / y_true.shape[0]

class LinearRegressor:

def __init__(self):

self.params = None

def fit(self, X: np.ndarray, y: np.ndarray):

r, _ = X.shape

X = np.hstack([np.ones((r, 1)), X])

self.params = np.linalg.inv(X.T @ X) @ X.T @ y

return self

def predict(self, X: np.ndarray):

r, _ = X.shape

return X @ self.params

if __name__ == "__main__":

regressor = RANSAC(model=LinearRegressor(), loss=square_error_loss, metric=mean_square_error)

X = np.array([-0.848,-0.800,-0.704,-0.632,-0.488,-0.472,-0.368,-0.336,-0.280,-0.200,-0.00800,-0.0840,0.0240,0.100,0.124,0.148,0.232,0.236,0.324,0.356,0.368,0.440,0.512,0.548,0.660,0.640,0.712,0.752,0.776,0.880,0.920,0.944,-0.108,-0.168,-0.720,-0.784,-0.224,-0.604,-0.740,-0.0440,0.388,-0.0200,0.752,0.416,-0.0800,-0.348,0.988,0.776,0.680,0.880,-0.816,-0.424,-0.932,0.272,-0.556,-0.568,-0.600,-0.716,-0.796,-0.880,-0.972,-0.916,0.816,0.892,0.956,0.980,0.988,0.992,0.00400]).reshape(-1,1)

y = np.array([-0.917,-0.833,-0.801,-0.665,-0.605,-0.545,-0.509,-0.433,-0.397,-0.281,-0.205,-0.169,-0.0531,-0.0651,0.0349,0.0829,0.0589,0.175,0.179,0.191,0.259,0.287,0.359,0.395,0.483,0.539,0.543,0.603,0.667,0.679,0.751,0.803,-0.265,-0.341,0.111,-0.113,0.547,0.791,0.551,0.347,0.975,0.943,-0.249,-0.769,-0.625,-0.861,-0.749,-0.945,-0.493,0.163,-0.469,0.0669,0.891,0.623,-0.609,-0.677,-0.721,-0.745,-0.885,-0.897,-0.969,-0.949,0.707,0.783,0.859,0.979,0.811,0.891,-0.137]).reshape(-1,1)

regressor.fit(X, y)

import matplotlib.pyplot as plt

plt.style.use("seaborn-darkgrid")

fig, ax = plt.subplots(1, 1)

ax.set_box_aspect(1)

plt.scatter(X, y)

line = np.linspace(-1, 1, num=100).reshape(-1, 1)

plt.plot(line, regressor.predict(line), c="peru")

plt.show()

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Parameters">Parameters</h2></div>

The threshold value to determine when a data point fits a model (t), and the number of inliers (data points fitted to the model within t) required to assert that the model fits well to data (d) are determined based on specific requirements of the application and the dataset, and possibly based on experimental evaluation. The number of iterations (k), however, can be roughly determined as a function of the desired probability of success (p) as shown below.

Let p be the desired probability that the RANSAC algorithm provides at least one useful result after running. In extreme (for simplifying the derivation), RANSAC returns a successful result if in some iteration it selects only inliers from the input data set when it chooses n points from the data set from which the model parameters are estimated. (In other words, all the selected n data points are inliers of the model estimated by these points). Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

A common case is that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> is not well known beforehand because of an unknown number of inliers in data before running the RANSAC algorithm, but some rough value can be given. With a given rough value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> and roughly assuming that the n points needed for estimating a model are selected independently (It is a rough assumption because each data point selection reduces the number of data point candidates to choose in the next selection in reality), <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w^{n}}</annotation>

</semantics>

</math><img src="./e922677e3162387632effeafb3f5f20a8ef0e9e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.883ex; height:2.343ex;" alt="{\displaystyle w^{n}}" loading="lazy"> is the probability that all n points are inliers and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-w^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-w^{n}}</annotation>

</semantics>

</math><img src="./4aac73a967e66683f946e9ae2d30ffdcce8565eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.885ex; height:2.509ex;" alt="{\displaystyle 1-w^{n}}" loading="lazy"> is the probability that at least one of the n points is an outlier, a case which implies that a bad model will be estimated from this point set. That probability to the power of k (the number of iterations in running the algorithm) is the probability that the algorithm never selects a set of n points which all are inliers, and this is the same as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-p}</annotation>

</semantics>

</math><img src="./9633a8692121eedfa99cace406205e5d1511ef8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.172ex; height:2.509ex;" alt="{\displaystyle 1-p}" loading="lazy"> (the probability that the algorithm does not result in a successful model estimation) in extreme. Consequently,

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-p=(1-w^{n})^{k}\,}</annotation>

</semantics>

</math><img src="./5e6c59636276747dbf9513fade4de0e14ab7f742.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.441ex; height:3.176ex;" alt="{\displaystyle 1-p=(1-w^{n})^{k}\,}" loading="lazy"></dd></dl>

which, after taking the <a href="Logarithm" title="Logarithm">logarithm</a> of both sides, leads to

<mfrac>

<mrow>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k={\frac {\log(1-p)}{\log(1-w^{n})}}}</annotation>

</semantics>

</math><img src="./c06fd8cf49f60f94a1e8579c1a6e8e8405e550bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:16.812ex; height:6.509ex;" alt="{\displaystyle k={\frac {\log(1-p)}{\log(1-w^{n})}}}" loading="lazy"></dd></dl>

This result assumes that the n data points are selected independently, that is, a point which has been selected once is replaced and can be selected again in the same iteration. This is often not a reasonable approach and the derived value for k should be taken as an upper limit in the case that the points are selected without replacement. For example, in the case of finding a line which fits the data set illustrated in the above figure, the RANSAC algorithm typically chooses two points in each iteration and computes <code>maybe_model</code> as the line between the points and it is then critical that the two points are distinct.

To gain additional confidence, the <a href="Standard_deviation" title="Standard deviation">standard deviation</a> or multiples thereof can be added to k. The standard deviation of k is defined as

<mfrac>

<msqrt>

<msup>

</mrow>

</msup>

</msqrt>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {SD} (k)={\frac {\sqrt {1-w^{n}}}{w^{n}}}}</annotation>

</semantics>

</math><img src="./d9362e4064b2a93abe120816fce8e9240275e219.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:18.845ex; height:5.843ex;" alt="{\displaystyle \operatorname {SD} (k)={\frac {\sqrt {1-w^{n}}}{w^{n}}}}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Advantages_and_disadvantages">Advantages and disadvantages</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

An advantage of RANSAC is its ability to do <a href="Robust_statistics" title="Robust statistics">robust estimation</a><a href="#cite_note-3">[3]</a> of the model parameters, i.e., it can estimate the parameters with a high degree of accuracy even when a significant number of <a href="Outlier" title="Outlier">outliers</a> are present in the data set. A disadvantage of RANSAC is that there is no upper bound on the time it takes to compute these parameters (except exhaustion). When the number of iterations computed is limited, the solution obtained may not be optimal, and it may not even be one that fits the data in a good way. In this way RANSAC offers a trade-off; by computing a greater number of iterations, the probability of a reasonable model being produced is increased. Moreover, RANSAC is not always able to find the optimal set even for moderately contaminated sets, and it usually performs badly when the number of inliers is less than 50%. Optimal RANSAC<a href="#cite_note-4">[4]</a> was proposed to handle both these problems and is capable of finding the optimal set for heavily contaminated sets, even for an inlier ratio under 5%. Another disadvantage of RANSAC is that it requires the setting of problem-specific thresholds.

RANSAC can only estimate one model for a particular data set. As for any one-model approach when two (or more) model instances exist, RANSAC may fail to find either one. The <a href="Hough_transform" title="Hough transform">Hough transform</a> is one alternative robust estimation technique that may be useful when more than one model instance is present. Another approach for multi-model fitting is known as PEARL,<a href="#cite_note-5">[5]</a> which combines model sampling from data points as in RANSAC with iterative re-estimation of inliers and the multi-model fitting being formulated as an optimization problem with a global energy function describing the quality of the overall solution.

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

The RANSAC algorithm is often used in <a href="Computer_vision" title="Computer vision">computer vision</a>, e.g., to simultaneously solve the <a href="Correspondence_problem" title="Correspondence problem">correspondence problem</a> and estimate the <a href="Fundamental_matrix_(computer_vision)" title="Fundamental matrix (computer vision)">fundamental matrix</a> related to a pair of stereo cameras; see also: <a href="Structure_from_motion" title="Structure from motion">Structure from motion</a>, <a href="Scale-invariant_feature_transform" title="Scale-invariant feature transform">scale-invariant feature transform</a>, <a href="Image_stitching" title="Image stitching">image stitching</a>, <a href="Rigid_motion_segmentation" title="Rigid motion segmentation">rigid motion segmentation</a>.

<div class="mw-heading mw-heading2"><h2 id="Development_and_improvements">Development and improvements</h2></div>

Since 1981 RANSAC has become a fundamental tool in the <a href="Computer_vision" title="Computer vision">computer vision</a> and image processing community. In 2006, for the 25th anniversary of the algorithm, a workshop was organized at the International <a href="Conference_on_Computer_Vision_and_Pattern_Recognition" title="Conference on Computer Vision and Pattern Recognition">Conference on Computer Vision and Pattern Recognition</a> (CVPR) to summarize the most recent contributions and variations to the original algorithm, mostly meant to improve the speed of the algorithm, the robustness and accuracy of the estimated solution and to decrease the dependency from user defined constants.

RANSAC can be sensitive to the choice of the correct noise threshold that defines which data points fit a model instantiated with a certain set of parameters. If such threshold is too large, then all the hypotheses tend to be ranked equally (good). On the other hand, when the noise threshold is too small, the estimated parameters tend to be unstable ( i.e. by simply adding or removing a datum to the set of inliers, the estimate of the parameters may fluctuate). To partially compensate for this undesirable effect, Torr et al. proposed two modification of RANSAC called MSAC (M-estimator SAmple and Consensus) and MLESAC (Maximum Likelihood Estimation SAmple and Consensus).<a href="#cite_note-6">[6]</a> The main idea is to evaluate the quality of the consensus set ( i.e. the data that fit a model and a certain set of parameters) calculating its likelihood (whereas in the original formulation by Fischler and Bolles the rank was the cardinality of such set). An extension to MLESAC which takes into account the prior probabilities associated to the input dataset is proposed by Tordoff.<a href="#cite_note-7">[7]</a> The resulting algorithm is dubbed Guided-MLESAC. Along similar lines, Chum proposed to guide the sampling procedure if some a priori information regarding the input data is known, i.e. whether a datum is likely to be an inlier or an outlier. The proposed approach is called PROSAC, PROgressive SAmple Consensus.<a href="#cite_note-8">[8]</a>

Chum et al. also proposed a randomized version of RANSAC called R-RANSAC <a href="#cite_note-9">[9]</a> to reduce the computational burden to identify a good consensus set. The basic idea is to initially evaluate the goodness of the currently instantiated model using only a reduced set of points instead of the entire dataset. A sound strategy will tell with high confidence when it is the case to evaluate the fitting of the entire dataset or when the model can be readily discarded. It is reasonable to think that the impact of this approach is more relevant in cases where the percentage of inliers is large. The type of strategy proposed by Chum et al. is called preemption scheme. Nistér proposed a paradigm called Preemptive RANSAC<a href="#cite_note-10">[10]</a> that allows real time robust estimation of the structure of a scene and of the motion of the camera. The core idea of the approach consists in generating a fixed number of hypotheses so that the comparison happens with respect to the quality of the generated hypothesis rather than against some absolute quality metric.

Other researchers tried to cope with difficult situations where the noise scale is not known and/or multiple model instances are present. The first problem has been tackled in the work by Wang and Suter.<a href="#cite_note-11">[11]</a> Toldo et al. represent each datum with the characteristic function of the set of random models that fit the point. Then multiple models are revealed as clusters which group the points supporting the same model. The clustering algorithm, called J-linkage, does not require prior specification of the number of models, nor does it necessitate manual parameters tuning.<a href="#cite_note-12">[12]</a>

RANSAC has also been tailored for recursive state estimation applications, where the input measurements are corrupted by outliers and <a href="Kalman_filter" title="Kalman filter">Kalman filter</a> approaches, which rely on a <a href="Normal_distribution" title="Normal distribution">Gaussian distribution</a> of the measurement error, are doomed to fail. Such an approach is dubbed KALMANSAC.<a href="#cite_note-13">[13]</a>

<div class="mw-heading mw-heading2"><h2 id="Related_methods">Related methods</h2></div>

<ul><li>MLESAC (Maximum Likelihood Estimate Sample Consensus) – <a href="Maximum_likelihood_estimation" title="Maximum likelihood estimation">maximizes the likelihood</a> that the data was generated from the sample-fitted model, e.g. a <a href="Mixture_model" title="Mixture model">mixture model</a> of inliers and outliers</li>

<li>MAPSAC (Maximum A Posterior Sample Consensus) – extends MLESAC to incorporate a <a href="Prior_probability" title="Prior probability">prior probability</a> of the parameters to be fitted and maximizes the <a href="Posterior_probability" title="Posterior probability">posterior probability</a></li>

<li>KALMANSAC – <a href="Causal_inference" title="Causal inference">causal inference</a> of the state of a <a href="Dynamical_system" title="Dynamical system">dynamical system</a></li>

<li><a href="Resampling_(statistics)" title="Resampling (statistics)">Resampling (statistics)</a></li>

<li>Hop-Diffusion Monte Carlo uses randomized sampling involve global jumps and local diffusion to choose the sample at each step of RANSAC for epipolar geometry estimation between very wide-baseline images.<a href="#cite_note-14">[14]</a></li>

<li>FSASAC (RANSAC based on data filtering and <a href="Simulated_annealing" title="Simulated annealing">simulated annealing</a>)<a href="#cite_note-15">[15]</a></li></ul>

<ul><li><a href="Hough_transform" title="Hough transform">Hough transform</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> Data Fitting and Uncertainty, T. Strutz, Springer Vieweg (2nd edition, 2016).

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCantzler" class="citation web cs1">Cantzler, H. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230204054340/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.3035&rep=rep1&type=pdf">"Random Sample Consensus (RANSAC)"</a>. Institute for Perception, Action and Behaviour, Division of Informatics, University of Edinburgh. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.3035">10.1.1.106.3035</a>. Archived from <a rel="nofollow" class="external text" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.3035&rep=rep1&type=pdf">the original</a> on 2023-02-04.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> Robust Statistics, Peter. J. Huber, Wiley, 1981 (republished in paperback, 2004), page 1.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> Anders Hast, Johan Nysjö, Andrea Marchetti (2013). "<a rel="nofollow" class="external text" href="http://wscg.zcu.cz/WSCG2013/!_2013_J_WSCG-1.pdf">Optimal RANSAC – Towards a Repeatable Algorithm for Finding the Optimal Set</a>". Journal of WSCG 21 (1): 21–30.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> Hossam Isack, Yuri Boykov (2012). "Energy-based Geometric Multi-Model Fitting". International Journal of Computer Vision 97 (2: 1): 23–147. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs11263-011-0474-7">10.1007/s11263-011-0474-7</a>.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> P.H.S. Torr and A. Zisserman, <a rel="nofollow" class="external text" href="http://www.academia.edu/download/3436793/torr_mlesac.pdf">MLESAC: A new robust estimator with application to estimating image geometry</a>, Journal of Computer Vision and Image Understanding 78 (2000), no. 1, 138–156.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> B. J. Tordoff and D. W. Murray, <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/abstract/document/1498749/">Guided-MLESAC: Faster image transform estimation by using matching priors</a>, IEEE Transactions on Pattern Analysis and Machine Intelligence 27 (2005), no. 10, 1523–1535.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <a rel="nofollow" class="external text" href="https://dspace.cvut.cz/bitstream/handle/10467/9496/2005-Matching-with-PROSAC-progressive-sample-consensus.pdf?sequence=1">Matching with PROSAC – progressive sample consensus</a>, Proceedings of Conference on Computer Vision and Pattern Recognition (San Diego), vol. 1, June 2005, pp. 220–226

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> O. Chum and J. Matas, Randomized RANSAC with Td,d test, 13th British Machine Vision Conference, September 2002. <a rel="nofollow" class="external free" href="http://www.bmva.org/bmvc/2002/papers/50/">http://www.bmva.org/bmvc/2002/papers/50/</a>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> D. Nistér, <a rel="nofollow" class="external text" href="https://pdfs.semanticscholar.org/e712/35d9e17f13186a4da6ee11eede0b64b01c95.pdf">Preemptive RANSAC for live structure and motion estimation</a>, IEEE International Conference on Computer Vision (Nice, France), October 2003, pp. 199–206.

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> H. Wang and D. Suter, <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/abstract/document/1335451/">Robust adaptive-scale parametric model estimation for computer vision</a>., IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (2004), no. 11, 1459–1474

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> R. Toldo and A. Fusiello, <a rel="nofollow" class="external text" href="https://pdfs.semanticscholar.org/0455/e5596d734e3dcf60c0179efb6404e62ceabb.pdf">Robust multiple structures estimation with J-linkage</a>, European Conference on Computer Vision (Marseille, France), October 2008, pp. 537–547.

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> A. Vedaldi, H. Jin, P. Favaro, and S. Soatto, <a rel="nofollow" class="external text" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.184.812&rep=rep1&type=pdf">KALMANSAC: Robust filtering by consensus</a>, Proceedings of the International Conference on Computer Vision (ICCV), vol. 1, 2005, pp. 633–640

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFBrahmachariSarkar2013" class="citation journal cs1">Brahmachari, Aveek S.; Sarkar, Sudeep (March 2013). "Hop-Diffusion Monte Carlo for Epipolar Geometry Estimation between Very Wide-Baseline Images". IEEE Transactions on Pattern Analysis and Machine Intelligence. 35 (3): 755–762. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTPAMI.2012.227">10.1109/TPAMI.2012.227</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/26353140">26353140</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2524656">2524656</a>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> W. Ruoyan and W. Junfeng, "<a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/9648331">FSASAC: Random Sample Consensus Based on Data Filter and Simulated Annealing</a>," in IEEE Access, vol. 9, pp. 164935-164948, 2021, doi: 10.1109/ACCESS.2021.3135416.

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFMartin_A._FischlerRobert_C._Bolles1981" class="citation journal cs1">Martin A. Fischler & Robert C. Bolles (June 1981). <a rel="nofollow" class="external text" href="http://apps.dtic.mil/dtic/tr/fulltext/u2/a460585.pdf">"Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography"</a> (PDF). Comm. ACM. 24 (6): 381–395. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F358669.358692">10.1145/358669.358692</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:972888">972888</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20141210132920/http://www.dtic.mil/dtic/tr/fulltext/u2/a460585.pdf">Archived</a> (PDF) from the original on December 10, 2014.</cite></li>

<li><cite id="CITEREFDavid_A._ForsythJean_Ponce2003" class="citation book cs1">David A. Forsyth & Jean Ponce (2003). Computer Vision, a modern approach. Prentice Hall. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-13-085198-7</bdi>.</cite></li>

<li><cite id="CITEREFRichard_Hartley_and_Andrew_Zisserman2003" class="citation book cs1">Richard Hartley and <a href="Andrew_Zisserman" title="Andrew Zisserman">Andrew Zisserman</a> (2003). Multiple View Geometry in Computer Vision (2nd ed.). Cambridge University Press.</cite></li>

<li><cite id="CITEREFStrutz2016" class="citation book cs1">Strutz, T. (2016). Data Fitting and Uncertainty (A practical introduction to weighted least squares and beyond). 2nd edition, Springer Vieweg. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-658-11455-8</bdi>.</cite></li>

<li><cite id="CITEREFP.H.S._TorrD.W._Murray1997" class="citation journal cs1">P.H.S. Torr & D.W. Murray (1997). "The Development and Comparison of Robust Methods for Estimating the Fundamental Matrix". International Journal of Computer Vision. 24 (3): 271–300. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1023%2FA%3A1007927408552">10.1023/A:1007927408552</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:12031059">12031059</a>.</cite></li>

<li><cite id="CITEREFOndrej_Chum2005" class="citation journal cs1">Ondrej Chum (2005). <a rel="nofollow" class="external text" href="http://cmp.felk.cvut.cz/~chum/papers/Chum-PhD.pdf">"Two-View Geometry Estimation by Random Sample and Consensus"</a> (PDF). PhD Thesis.</cite></li>

<li><cite id="CITEREFSunglok_ChoiTaemin_KimWonpil_Yu2009" class="citation journal cs1">Sunglok Choi; Taemin Kim & Wonpil Yu (2009). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20200831001552/http://www.bmva.org/bmvc/2009/Papers/Paper355/Paper355.pdf">"Performance Evaluation of RANSAC Family"</a> (PDF). In Proceedings of the British Machine Vision Conference (BMVC). Archived from <a rel="nofollow" class="external text" href="http://www.bmva.org/bmvc/2009/Papers/Paper355/Paper355.pdf">the original</a> (PDF) on 2020-08-31. Retrieved 2010-10-01.</cite></li></ul>

<ul><li><cite id="CITEREFAnders_HastJohan_NysjöAndrea_Marchetti2013" class="citation journal cs1">Anders Hast; Johan Nysjö; Andrea Marchetti (2013). <a rel="nofollow" class="external text" href="http://www.cb.uu.se/~aht/articles/A53-full.pdf">"Optimal RANSAC – Towards a Repeatable Algorithm for Finding the Optimal Set"</a> (PDF). Journal of WSCG. 21 (1): 21–30.</cite></li>

<li><cite id="CITEREFHossam_IsackYuri_Boykov2012" class="citation journal cs1">Hossam Isack; Yuri Boykov (2012). <a rel="nofollow" class="external text" href="http://www.csd.uwo.ca/~yuri/Papers/tr735.pdf">"Energy-based Geometric Multi-Model Fitting"</a> (PDF). International Journal of Computer Vision. 97 (2: 1): 23–147. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.381.2434">10.1.1.381.2434</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs11263-011-0474-7">10.1007/s11263-011-0474-7</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5461268">5461268</a>.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-11-22" href="https://en.wikipedia.org/wiki/?title=Random_sample_consensus&oldid=1258988090">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>